10739. String to Palindrome

In this problem you are asked to convert a string into a palindrome with minimum number of operations. The operations are described below. Here you’d have the ultimate freedom. You are allowed to:

· Add any character at any position

· Remove any character from any position

· Replace any character at any position with another character

Every operation you do on the string would count for a unit cost. You'd have to keep that as low as possible.

For example, to convert “abccda" you would need at least two operations if we allowed you only to add characters. But when you have the option to replace any character you can do it with only one operation. We hope you’d be able to use this feature to your advantage.

Input. Contains several test cases. The first line gives you the number of test cases T (1 ≤ T ≤ 10). Then T test cases will follow, each in one line. The input for each test case consists of a string containing lower case letters only. You can safely assume that the length of this string will not exceed 1000 characters.

Output. For each set of input print the test case number first. Then print the minimum number of characters needed to turn the given string into a palindrome.

Sample Input

6

tanbirahmed

shahriarmanzoor

monirulhasan

syedmonowarhossain

sadrulhabibchowdhury

mohammadsajjadhossain

Sample Output

Case 1: 5

Case 2: 7

Case 3: 6

Case 4: 8

Case 5: 8

Case 6: 8

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть f(i, j) содержит наименьшее количество операций, за которое можно преобразовать строку S_i..j в палиндром.

1. Если строка состоит из одной буквы или является пустой, то она является палиндромом: f(i, j) = 0 при j – i < 1.

2. Если S_i = S_j, то строка S_i..j является палиндромом только если палиндромом является S_i+1..j-1. В этом случае f(i, j) = f(i + 1, j – 1).

3. Иначе следует рассмотреть три варианта преобразования строки:

· удаляем первый символ: f(i, j) = 1 + f(i + 1, j);

· удаляем последний символ: f(i, j) = 1 + f(i, j – 1);

· заменяем последний символ на первый: f(i, j) = 1 + f(i + 1, j – 1);

Или то же самое что f(i, j) = 1 + min(f(i + 1, j), f(i, j – 1), f(i + 1, j – 1));

Реализация алгоритма

#include <cstdio>

#include <cstring>

#include <algorithm>

#define MAX 1001

using namespace std;

char s[MAX];

int dp[MAX][MAX];

int i, j, t, n, len;

int f(int i, int j)

{

if (j - i < 1) return 0;

if (dp[i][j] != -1) return dp[i][j];

if (s[i] == s[j]) return dp[i][j] = f(i+1,j-1);

return dp[i][j] = 1 + min(min(f(i+1,j),f(i,j-1)),f(i+1,j-1));

}

int main(void)

{

scanf("%d\n",&n);

for(t = 1; t <= n; t++)

{

gets(s); len = strlen(s);

memset(dp,-1,sizeof(dp));

printf("Case %d: %d\n",t,f(0,len-1));

}

}